package cn.edu.jxau.util;

import java.util.Iterator;
import java.util.NoSuchElementException;

public class LinkedList<T> extends List<T> {

    /**
     * 列表元素个数
     */
    private int size;

    /**
     * 列表头指针
     */
    private Node<T> first;

    public LinkedList() {
        first = new Node<>(); // 有头结点
    }
    
    public void reverse() {
        first.next = reverse(first.next);
    }
    
    /**
     * 用迭代的方式逆序数组
     * @param first
     * @return
     */
//    private Node<T> reverse(Node<T> first) {
//        
//        Node<T> reverse = null;
//        while(first != null) {
//            
//            Node<T> second = first.next;
//            first.next = reverse;
//            reverse = first;
//            first = second;
//        }
//        return reverse;
//    }
    
    /**
     * 用递归的方式逆序数组
     * @param first
     * @return
     */
    private Node<T> reverse(Node<T> first) {
        
        if(first == null) {
            return null;
        }
        if(first.next == null) {
            return first;
        }
        Node<T> second = first.next;
        Node<T> reverse = reverse(second);
        second.next = first;
        first.next = null;
        return reverse;
    }
	
    //...
    //...
	//...
	
	private class Node<T> {
        private T item;
        private Node<T> next;

        public Node() {

        }

        public Node(T item) {
            this.item = item;
        }
    }
}
